1. Field of the Invention
The present invention relates to methods of model-order reduction and sensitivity analysis for VLSI interconnect circuits, and more particularly to a method of one-sided projection.
2. Description of Related Art
With considering the issues of the signal integrity in high-speed VLSI designs, interconnects are often modeled as lumped RLC networks. To analyze an RLC linear network, the modified nodal analysis (MNA) can be used as follows:
                                                                        M                ⁢                                                      ⅆ                                          x                      ⁡                                              (                        t                        )                                                                                                  ⅆ                    t                                                              =                                                -                                      Nx                    ⁡                                          (                      t                      )                                                                      +                                  Bu                  ⁡                                      (                    t                    )                                                                                                                                                            y                  ⁡                                      (                    t                    )                                                  =                                                      D                    T                                    ⁢                                      x                    ⁡                                          (                      t                      )                                                                                  ,                                                          (        1        )            
where M,N∈Rn×n,x,B∈Rn×m, D∈Rn×p and y∈Rp×m. Matrices M and N containing capacitances, inductances, conductances and resistances are positive definite. The state matrix x(t) contains node voltages and branch currents of inductors, and u(t) and y(t) represent inputs and outputs. The adjoint equation associated with the system in Eq. (1) is of the form
                                          M            ⁢                                          ⅆ                                                      x                    a                                    ⁡                                      (                    t                    )                                                                              ⅆ                t                                              =                                    -                                                Nx                  a                                ⁡                                  (                  t                  )                                                      +                          Du              ⁡                              (                t                )                                                    ,                            (        2        )            
which is the modified node equation of the adjoint network (or the dual system). If the m-port transfer functions are concerned, then p=m and D=B. The transfer functions of the state variables and of the outputs are X(s)=(N+sM)−1B and Y(s)=BTX(s). Conversely, those of the corresponding adjoint network are given asXa(s)=(NT+sM)−1B.
Since the computational cost for simulating such large circuits is indeed tremendously huge, model-order reduction techniques have been proposed recently to reduce the computational complexity, for example, U.S. Pat. No. 5,313,398, U.S. Pat. No. 5,379,231, U.S. Pat. No. 5,537,329, U.S. Pat. No. 5,689,685, U.S. Pat. No. 5,920,484, U.S. Pat. No. 6,023,573, U.S. Pat. No. 6,041,170. Among these ways, the moment matching techniques based on Pade approximation and Krylov subspace projections take advantage of efficiency and numerical stability.
‘Moment’ can be defined as follows. By expanding Y(s) about a frequency s0∈C, we have
            Y      ⁡              (        s        )              =                            ∑                      i            =                          -              ∞                                ∞                ⁢                                  ⁢                                            Y                              (                i                )                                      ⁡                          (                              s                0                            )                                ⁢                                    (                              s                -                                  s                  0                                            )                        i                              =                        ∑                      i            =                          -              ∞                                ∞                ⁢                              B            T                    ⁢                                    X                              (                i                )                                      ⁡                          (                              s                0                            )                                ⁢                                    (                              s                -                                  s                  0                                            )                        i                                ,whereX(i)(s0)=(−(N+s0M)−1M)i(N+s0M)−1Bis the i th-order system moment of X(s) about s0 and Y(i)(s0) is the corresponding output moment. Similarly, the i th-order system moment of Xa(s) about s0,Xa(i)(s0)=(−(NT+s0M)−1M)i(NT+s0M)−1B,
can be obtained.
In general, Krylov subspace projection methods can be divided into two categories: one-sided projection methods and two-sided projection methods. The one-sided projection methods use the congruence transformation to generate passive reduced-order models while the two-sided ones can not be guaranteed.
The one-sided projection method for moment matching to generate a reduced-order network of Eq. (1) is described as follows. First, a congruence transformation matrix Vq can be generated by the Krylov subspace methods. Let A=−(N+s0M)−1M and R=(N+s0M)−1B . The k th-order block Krylov subspace generated by A and R is defined asK(A,R,k)=colsp{R,AR, . . . ,Ak−1R}=colsp(Vq),  (3)where q≦km. colsp(Vq) represents span the vector space by columns of matrix Vq. The Krylov subspace K(A,R,k) is then equal to the subspace spanned by system moments X(i)(s0) for i=0,1, . . . ,k−1. Matrix Vq can be iteratively generated by the block Arnoldi algorithm and thus be an orthonormal matrix. Next, by applying Vq, n-dimensional state space can be projected onto a q-dimensional space, where q<<n: x(t)=Vq{circumflex over (x)}(t). Then the reduced-order model can be calculated as{circumflex over (M)}=VqTMVq,{circumflex over (N)}=VqTNVq,{circumflex over (B)}=VqTB.  (4)The transfer function of the reduced network isŶ(s)={circumflex over (B)}T({circumflex over (N)}+s{circumflex over (M)})−1{circumflex over (B)}.The corresponding i th-order output moment about s0 isŶ(i)={circumflex over (B)}T(−({circumflex over (N)}+s0{circumflex over (M)})−1{circumflex over (M)})({circumflex over (N)}+s0{circumflex over (M)})−1{circumflex over (B)}.
It can be shown that Y(i)(s0)=Ŷ(i)(s0) for i=0,1, . . . ,k−1 and the reduced-order model is passive.
However, linear independence of the columns in the block Krylov sequence, {R,AR, . . . ,Ak−1R}, is lost only gradually in general. In addition, the orthogonalization process to generate matrix Vq may be numerically ill-conditioned if the order k is extremely high. This invention will provide the adjoint network technique to overcome the above problem. Furthermore, the method will reduce the computational cost of constructing the projector.